COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "let.pub[let,jmc]" source
C00006 ENDMK
C⊗;
.require "let.pub[let,jmc]" source;
∂CSL Prof. Judea Pearl↓Computer Science Department↓UCLA↓Los Angeles, CA 90024∞

Dear Judea:

	Thanks for the chapters of your book analyzing αα-β with
"informed ordering".  I haven't read them yet.

	So far as I know, 1956 was the first time anyone thought of
αα-β.  The Russians thought of it independently and published in 1963.
I don't remember what Knuth published so I'll start over.
There is no record of the Dartmouth discussions.

	My idea mixed the αα-β idea with that of using optimistic and
pessimistic evaluations.  Therefore, while I knew that αα-β avoided
some absolutely unnecessary computations, it didn't occur to me that
the simple αα-β could be proved to give the same result as minimax.
It seems to me that I learned about this from Tim Hart.  Roland Silver
and Michael Levin may also have been involved.

	I also didn't know about Knuth's weak and strong forms of the algorithm.
It seems to me that I always explained the strong form, but the LISP
program that I used to explain it on blackboards had a bug so that it
only did the weak form.

.reg

P.S. I did look at section 9.4, and I have one remark.  The evaluation
for move ordering should not be the same as the static evaluation that
would be used in choosing a move.  Firstly, it can afford to be more
adventurous including queen sacrifices, etc.  Considerations include
the expected time to evaluate it (Most queen sacrifices are quickly
seen to be bad.) and an aspiration level.  We look first at moves
that have some chance of reaching an aspiration level.  I have some
doubt about your results that the functions are flat near good orderings.
Of course, the key item is getting the an adequate move first.  If
this is accomplished, it doesn't matter how the others are ordered.
I wish I had time to go through your mathematics and compare it with
my intuitive ideas.

	Realistic mathematical models involving the work expended on ordering
the moves and work involved in the tree search itself seem difficult
to discover and even more difficult to compute with.  It seems even
harder than the "two arm bandit" problems the RAND people worked on
starting in the 1950s.